package data_structures_and_algorithms.list_node;

import common.ListNode;

import java.util.PriorityQueue;

/**
 * @ClassName Code_0023_mergeKSortedLists
 * @Description: https://leetcode.cn/problems/merge-k-sorted-lists/
 * @Author: myl
 * @create_time: 2022/10/27 23:24
 */
public class Code_0023_mergeKLists {

    // 构造优先队列，分别将数组中的链表头结点设置进去
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null)// lists中的元素可能为null，所以需要判断下
                pq.offer(lists[i]);
        }

        while (!pq.isEmpty()){
            ListNode node = pq.poll();
            if (node.next != null){
                pq.offer(node.next);
            }
            cur.next = node;
            cur = cur.next;
        }
        return head.next;
    }
}
